home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / MPW_TOOL / TOOLS / TOOLS_WI / BYACC__ / WARSHALL.C < prev    next >
Text File  |  1989-11-19  |  2KB  |  96 lines
  1. /************************************************************************
  2. *                                    *
  3. *  This file contains routines for computing the transitive closure    *
  4. *  and the reflexive transitive closure of a relation using Warshall's    *
  5. *  algorithm.                                *
  6. *                                    *
  7. ************************************************************************/
  8.  
  9. #include "dep.h"
  10.  
  11. transitive_closure(R, n)
  12. unsigned *R;
  13. int n;
  14. {
  15.   register int rowsize;
  16.   register unsigned mask;
  17.   register unsigned *rowj;
  18.   register unsigned *rp;
  19.   register unsigned *rend;
  20.   register unsigned *ccol;
  21.  
  22.   unsigned *relend;
  23.   unsigned *cword;
  24.   unsigned *rowi;
  25.  
  26.   rowsize = ROWSIZE(n);
  27.   relend = (unsigned *) ((unsigned long) R + n*rowsize);
  28.  
  29.   cword = R;
  30.   mask = 1;
  31.   rowi = R;
  32.   while (rowi < relend)
  33.     {
  34.       ccol = cword;
  35.       rowj = R;
  36.  
  37.       while (rowj < relend)
  38.     {
  39.       if (*ccol & mask)
  40.         {
  41.           rp = rowi;
  42.           rend = (unsigned *) ((unsigned long) rowj + rowsize);
  43.  
  44.           while (rowj < rend)
  45.         *rowj++ |= *rp++;
  46.         }
  47.       else
  48.         {
  49.           rowj = (unsigned *) ((unsigned long) rowj + rowsize);
  50.         }
  51.  
  52.       ccol = (unsigned *) ((unsigned long) ccol + rowsize);
  53.     }
  54.  
  55.       mask <<= 1;
  56.       if (mask == 0)
  57.     {
  58.       mask = 1;
  59.       cword++;
  60.     }
  61.  
  62.       rowi = (unsigned *) ((unsigned long) rowi + rowsize);
  63.     }
  64. }
  65.  
  66. reflexive_transitive_closure(R, n)
  67. unsigned *R;
  68. int n;
  69. {
  70.   register int rowsize;
  71.   register unsigned mask;
  72.   register unsigned *rp;
  73.   register unsigned *relend;
  74.  
  75.   transitive_closure(R, n);
  76.  
  77.   rowsize = ROWSIZE(n);
  78.   relend = (unsigned *) ((unsigned long) R + n*rowsize);
  79.  
  80.   mask = 1;
  81.   rp = R;
  82.   while (rp < relend)
  83.     {
  84.       *rp |= mask;
  85.  
  86.       mask <<= 1;
  87.       if (mask == 0)
  88.     {
  89.       mask = 1;
  90.       rp++;
  91.     }
  92.  
  93.       rp = (unsigned *) ((unsigned long) rp + rowsize);
  94.     }
  95. }
  96.